package labuladong.BFS.打开转盘锁;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class 转盘锁 {

    /**
     * 向上拨动
     * @param s 传进来的密码串
     * @param i 需要拨动的位置
     * @return
     */
    public static String plusOne(String s, int i) {
        char[] ch = s.toCharArray();
        if(ch[i] == '9') {
            ch[i] = '0';
        } else {
            ch[i] += 1;
        }
        return new String(ch);
    }

    /**
     * 向下拨动
     * @param s 传进来的密码串
     * @param i 需要拨动的位置
     * @return
     */
    public static String minusOne(String s, int i) {
        char[] ch = s.toCharArray();
        if (ch[i] == '0') {
            ch[i] = '9';
        } else {
            ch[i] -= 1;
        }
        return new String(ch);
    }

    public static int bfs (String[] deadends, String target) {
        Set<String> deadendsSet = new HashSet<>();
        Set<String> vistor = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        int steps = 0;
        for (String s : deadends) {
            deadendsSet.add(s);
        }
        queue.offer("0000");
        vistor.add("0000");
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int j=0; j<size; j++) {
                String cur = queue.poll();
                if (cur.equals(target)) return steps;
                if (deadendsSet.contains(cur)) continue;
                for (int i=0; i<4; i++) {
                    String str1 = plusOne(cur, i);
                    if (!vistor.contains(str1)) {
                        queue.offer(str1);
                        vistor.add(str1);
                    }
                    String str2 = minusOne(cur, i);
                    if (!vistor.contains(str2)) {
                        queue.offer(str2);
                        vistor.add(str2);
                    }
                }
            }
            steps++;
        }
        return -1;
    }


    public static void main(String[] args) {
        System.out.println(bfs(new String[]{"0201","0101","0102","1212","2002"}, "0202"));
    }
}
